package de.hska.algo.labor2010.strecken;


import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;



public class Grid {
	private double minX, maxX, minY, maxY;
	private ArrayList<GridPart> grid;
	

	public Grid(int n, int imgWidth) {
		grid = new ArrayList<GridPart>(n * n);
		
	}

	public Grid(int n) {
		grid = new ArrayList<GridPart>(n * n);
		
	}

	public Grid() {
		grid = new ArrayList<GridPart>(10 * 10);
		
	}

	public void initialize(List<Line> lines, int n) {

		setBorders(lines);
		createGridParts(n);
		for (Line line : lines) {

			sortLineInGridBresenham(line);
		}

	}

	public List<Point> intersect(List<Line> someLines) {
		List<Point> result = new ArrayList<Point>();
		for (GridPart part : grid) {
			result.addAll(part.findIntersections());
		}
		return result;

	}

	public List<Point> intersectAndInitialize(List<Line> someLines, int n) {
		initialize(someLines, n);
		return intersect(someLines);
	}

	private void createGridParts(int n) {
		this.grid = new ArrayList<GridPart>(n * n);
		double width, height;

		width = (maxX - minX +1) / (n);
		height = (maxY - minY +1) / (n);
	
		System.out.println(minX + " " + minY + " " + maxX + " " + maxY);
		System.out.println("each grid is " + width + " long and " + height
				+ " high");
		// System.out.println("You ordered " + n * n + " grids");
		double right, bottom, left, top;
		// set Start
		right = minX;
		left = right + width;
		for (int i = 0; i < n; i++) {
			
			bottom=minY;
			top = bottom + height;
			for (int j = 0; j < n; j++) {
				grid.add(new GridPart(right, bottom, left, top));
				bottom = top;
				top += height;
			}
			right = left;
			left += width;
		}

		addNeighbors(n);

		System.out.println("I created the grid and it has " + grid.size()
				+ " parts");
	}

	private void addNeighbors(int n) {
		for (int i = 0; i < grid.size(); i++) {
			if (i < n) {
				if (i != n - 1) {
					grid.get(i).addNeighbor(grid.get(i + 1));
				}
				grid.get(i).addNeighbor(grid.get(i + n + 1));
				if (i != 0) {
					grid.get(i).addNeighbor(grid.get(i - 1));
					grid.get(i).addNeighbor(grid.get(i + n - 1));
				}
				grid.get(i).addNeighbor(grid.get(i + n));
			} else if (i >= n * n - n) {
				if (i != n * n - 1) {
					grid.get(i).addNeighbor(grid.get(i + 1));
					grid.get(i).addNeighbor(grid.get(i - n + 1));
				}
				if (i != n * n - n) {
					grid.get(i).addNeighbor(grid.get(i - 1));
					grid.get(i).addNeighbor(grid.get(i - n - 1));
				}

				grid.get(i).addNeighbor(grid.get(i - n));

			} else {

				if ((i + 1) % n != 0) {
					grid.get(i).addNeighbor(grid.get(i + 1));
					grid.get(i).addNeighbor(grid.get(i - n + 1));
					grid.get(i).addNeighbor(grid.get(i + n + 1));
				}
				if ((i % n) != 0) {
					grid.get(i).addNeighbor(grid.get(i + n - 1));
					grid.get(i).addNeighbor(grid.get(i - n - 1));
					grid.get(i).addNeighbor(grid.get(i - 1));
				}

				grid.get(i).addNeighbor(grid.get(i - n));

				grid.get(i).addNeighbor(grid.get(i + n));

			}
		}
	}

	private void setBorders(List<Line> someLines) {
		minX = someLines.get(0).getP1().getX();
		maxX = someLines.get(0).getP2().getX();
		if (someLines.get(0).getP1().getY() < someLines.get(0).getP2().getY()) {
			minY = someLines.get(0).getP1().getY();
			maxY = someLines.get(0).getP2().getY();
		} else {
			maxY = someLines.get(0).getP1().getY();
			minY = someLines.get(0).getP2().getY();
		}
		for (int i = 0; i < someLines.size(); i++) {
			if (someLines.get(i).getP1().getX() < minX) {
				minX = someLines.get(i).getP1().getX();
			}

			if (someLines.get(i).getP2().getX() > maxX) {
				maxX = someLines.get(i).getP2().getX();
			}

			if (someLines.get(i).getP1().getY() < someLines.get(i).getP2()
					.getY()) {
				if (someLines.get(i).getP2().getY() > maxY) {
					maxY = someLines.get(i).getP2().getY();
				}
				if (someLines.get(i).getP1().getY() < minY) {
					minY = someLines.get(i).getP1().getY();
				}
			} else {
				if (someLines.get(i).getP1().getY() > maxY) {
					maxY = someLines.get(i).getP1().getY();
				}
				if (someLines.get(i).getP2().getY() < minY) {
					minY = someLines.get(i).getP2().getY();
				}
			}

		}

	}

	private void sortLineInGridBresenham(Line someLine) {
		List<GridPart> parts = null;
		try {
			 parts = grid;	
		} catch (Exception e) {
			System.out.println("You need to set up the grid bevor trying to intersect lines.");
			return;
		}
		// System.out.println("starting sort algorithm for  line" + someLine);
		
		setInsidesFalse();
//		int x0 = (int) (someLine.getP1().getX() *100.0  );
//		int x1 = (int) (someLine.getP2().getX() *100.0);
//		int y0 = (int) (someLine.getP1().getY() *100.0);
//		int y1 = (int) (someLine.getP2().getY()*100.0);

		int x0 = (int) Math.round(someLine.getP1().getX());
		int x1 = (int) Math.round(someLine.getP2().getX());
		int y0 = (int) Math.round(someLine.getP1().getY());
		int y1 = (int) Math.round(someLine.getP2().getY());

		int dx = (x1 - x0); 
		int incX = 1;
		int dy = Math.abs(y1 - y0); 
		int incY = y1 > y0 ? 1 : -1;
		//int sum = dx +dy;
		int sum = dx > dy? dx : Math.abs(dy);
		Point tmp;
		
		
//		while (!(x0 == x1 && y0 == y1)) {
		while ((x0 < x1 || incY * y0 < incY * y1)) {
//			tmp = new Point(x0 /10.0, y0/10.0 );
			tmp = new Point(x0, y0);
			// sort this Point (line) into a grid

				
		
			for (GridPart aGrid : parts) {
				if (!aGrid.getThisLineisInside()
						&& aGrid.isPointInGridPart(tmp)) {
					aGrid.addLine(someLine);
					aGrid.setThisLineisInside(true);
					parts = aGrid.getNeighbors();
					aGrid = parts.get(0);
					break;
				}

			}
			// now update Point
			// walk into fast direction and update slow direction if necessary
//			if (dx >= Math.abs(dy)) {
//				x0 += incX;
//				dx -= incX;
//				if (2 * dy > dx) {
//					y0 += incY;
//					dy -= Math.abs(incY);
//				}
//			} else {
//				y0 += incY;
//				dy -= incY;
//				if (2 * dx > dy) {
//					x0 += incX;
//					dx -= incX;
//				}
			if (dx >= Math.abs(dy)) {
				x0 += incX;
				//dx -= incX;
				sum-= 2*dy;
				if (sum < 0) {
					y0 += incY;
					//dy -= Math.abs(incY);
					sum+=2*dx;
				}
			} else {
				y0 += incY;
				//dy -= incY;
				sum-=  2*dx;
				if (sum<0) {
					x0 += incX;
					//dx -= incX;
					sum+=2*dy;
				}

				//System.out.println("Point updated: " + x0 + ", " + y0);
			}
			
		}
		
	}
	

	private void setInsidesFalse() {
		for (GridPart aGrid : grid)
			aGrid.setThisLineisInside(false);
	}

	public String toString() {
		String grid = new String();
		int last = 0;
		if (this.grid.size() > 0) {
			last = this.grid.size() - 1;
			grid += "Grid Borders are:" + this.grid.get(0).getLowerLeft() + " "
					+ this.grid.get(last).getUpperRight() + "\n";
		}
		int i = 0;
		for (GridPart part : this.grid) {
			grid += "Grid number: " + i + ": ";
			grid += part.toString() + "\n";
			i++;
		}
		return grid;

	}

	public double getMinX() {
		return minX;
	}

	public double getMaxX() {
		return maxX;
	}

	public double getMinY() {
		return minY;
	}

	public double getMaxY() {
		return maxY;
	}

	public ArrayList<GridPart> getGrid() {
		return grid;
	}

	
	

	

	// private void drawPoint(Point p) {
	// Graphics2D g = img.createGraphics();
	// g.setColor(Color.RED);
	// g.setStroke(new BasicStroke(2));
	// g.drawRect((int) (p.getX() * 10), (int) (p.getY() * 10), 2, 2);
	// System.out.println(p);
	//
	// }
}